package com.hyb.algorithm.data.struct.dp;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * @Author: huyanbing
 * @Date: 2021/8/12 11:08 上午
 * <p>
 * https://leetcode.wang/leetCode-51-N-Queens.html
 */
public class SolveNQueens2 {


    public static void main(String[] args) {

        SolveNQueens2 solveNQueens2 = new SolveNQueens2();

        List<List<String>> ret = solveNQueens2.solveNQueens(4);

        for (List<String> list : ret) {

            for (String str : list) {
                System.out.println(str);
            }

            System.out.println();
        }
    }


    public List<List<String>> solveNQueens(int n) {


        //行队列   currentRowQueue.size 代表第几行
        List<Integer> currentRowQueue = new ArrayList<>();


        //返回结果
        List<List<String>> ret = new ArrayList<>();


        processCurrentRow(currentRowQueue, n, ret);

        return ret;

    }

    /**
     * 一行一行 开始放皇后
     *
     * @param currentRowQueue
     * @param n
     * @param ret
     */
    private void processCurrentRow(List<Integer> currentRowQueue, int n, List<List<String>> ret) {

        //如何 行数==n 表示已经满了
        if (currentRowQueue.size() == n) {

            //一个结果 一个 列表
            List<String> subRet = new ArrayList<>();
            //按行填充 .
            for (int i = 0; i < n; i++) {
                char[] arr = new char[n];
                Arrays.fill(arr, '.');

                //找到第几列放皇后
                int col = currentRowQueue.get(i);
                arr[col] = 'Q';

                String rowStr = new String(arr);

                subRet.add(rowStr);
            }

            //把 整个结果 放入大 list 中
            ret.add(subRet);

            return;
        }


        //按列循环
        for (int col = 0; col < n; col++) {

            //判断当前行 是不是包括该列
            if(currentRowQueue.contains(col)){
                continue;
            }

            //判断对角线是不是有皇后
            if (isInDiagonal(currentRowQueue, col)) {
                continue;
            }

            //将该列放入皇后
            currentRowQueue.add(col);

            //继续处理下一行
            processCurrentRow(currentRowQueue, n, ret);


            //将当前列的皇后移除，去判断下一列
            //进入这一步就是两种情况，下边的行走不通了回到这里或者就是已经拿到了一个解回到这里
            currentRowQueue.remove(currentRowQueue.size() - 1);

        }
    }


    /**
     * 判断是否在同一个对角线  因为是一行一行的放的 所以 不存在旁边相隔的情况
     *
     *
     * 时间复杂度：
     *
     * 空间复杂度：
     *
     * 上边我们只判断了列冲突和对角线冲突，至于行冲突，由于我们采取一行一行加皇后，所以一行只会有一个皇后，不会产生冲突。
     * @param currentRowQueue
     * @param col
     * @return
     */
    private boolean isInDiagonal(List<Integer> currentRowQueue, int col) {

        int currentRow = currentRowQueue.size();
        int currentCol = col;

        for (int row = 0; row < currentRowQueue.size(); row++) {
            if (Math.abs(currentRow - row) == Math.abs(currentCol - currentRowQueue.get(row))) {
                return true;
            }
        }

        return false;
    }


}
